// 题目描述
// 438. 找到字符串中所有字母异位词
// 中等
// 59
// 给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
// 变位词 指字母相同，但排列不同的字符串。
//   示例 1：
// 输入: s = "cbaebabacd", p = "abc"
// 输出: [0,6]
// 解释:
// 起始索引等于 0 的子串是 "cba", 它是 "abc" 的变位词。
// 起始索引等于 6 的子串是 "bac", 它是 "abc" 的变位词。
//  示例 2：
// 输入: s = "abab", p = "ab"
// 输出: [0,1,2]
// 解释:
// 起始索引等于 0 的子串是 "ab", 它是 "ab" 的变位词。
// 起始索引等于 1 的子串是 "ba", 它是 "ab" 的变位词。
// 起始索引等于 2 的子串是 "ab", 它是 "ab" 的变位词。
//   提示:
// 1 <= s.length, p.length <= 3 * 104
// s 和 p 仅包含小写字母
//   注意：本题与主站 438 题相同： https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/
// 通过次数
// 36.9K
// 提交次数
// 60K
// 通过率
// 61.5%
// https://leetcode.cn/problems/find-all-anagrams-in-a-string/

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
  const needs = new Map()
  for (const ch of p) {
    needs.set(ch, (needs.get(ch) || 0) + 1)
  }
  const win = new Map()
  const ans = []

  let left = 0, right = 0, valid = 0
  while (right < s.length) {
    // 初始不是子串
    // 放入窗口
    const ch = s[right++]
    // 为了提高比较效率，这里 map 只放入 needs 中包含的字符
    // 可以理解 left, right 是窗口内的字符
    // map 中放了，needs 中包含的字符
    if (needs.has(ch)) {
      win.set(ch, (win.get(ch) || 0) + 1)
      if (win.get(ch) === needs.get(ch)) {
        ++valid
      }
    }

    // 是子串
    while ((right - left) === p.length) {
      // 是字串才能成为异位词，所以在这里更新答案
      if (valid === needs.size) {
        ans.push(left)
      }

      // 弹出窗口
      const last = s[left++]
      if (needs.has(last)) {
        if (win.get(last) === needs.get(last)) {
          --valid
        }
        win.set(last, win.get(last) - 1)
      }
    }
  }

  return ans
}

console.log(
  findAnagrams(
    'baa',
    'aa'
  )
)
